/*
 * =====================================================================================
 *
 *       Filename:  longest_increase_sequence.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  02/19/2000 01:32:06 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Chen Ken (Ken), zlchen.ken@gmail.com
 *        Company:  EMC
 *
 * =====================================================================================
 */

#include <cstdio>
#include <vector>

using namespace std;

template<typename T> 
vector<T> find_lis(const vector<T> &seq)
{
	vector<T> longestSubSeqIndex, prev(seq.size());
 
	if (seq.size() < 1) return longestSubSeqIndex;
	longestSubSeqIndex.push_back(0);
 
	int high, low;
	for(int i = 1; i < (int)seq.size(); i++)
	{
		if (seq[longestSubSeqIndex.back()] < seq[i])
		{
			prev[i] = longestSubSeqIndex.back();
			longestSubSeqIndex.push_back(i);
			continue;
		}
 
		for(low = 0, high = longestSubSeqIndex.size() - 1; low < high;)
		{  //Binary search
			int mid = (low + high) / 2;
			if(seq[longestSubSeqIndex[mid]] < seq[i])
			{
        low = mid + 1; 
			}
			else
			{
        high = mid;
			}
		}
 
		if(seq[i] < seq[longestSubSeqIndex[low]])
		{
			if(low > 0)
			{
        prev[i] = longestSubSeqIndex[low-1]; // 为了找到长度为u的前一个元素，即长度为u-1的
			}
			longestSubSeqIndex[low] = i;			       // 元素的位置
		}
	}
 
	for(int len = longestSubSeqIndex.size(), preIndex = longestSubSeqIndex.back(); len--; preIndex = prev[preIndex]) 
	{
		longestSubSeqIndex[len] = preIndex;
	}

	return longestSubSeqIndex;
}

int main()
{
	int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
	vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
	vector<int> lis = find_lis(seq);
 
	for (unsigned i = 0; i < lis.size(); i++)
		printf(i+1 < lis.size() ? "%d " : "%d\n", seq[lis[i]]);
 
	return 0;
}

